131 分割回文串

给你一个字符串  s ，请你将  s  分割成一些 子串，使每个子串都是 回文串 。返回  s  所有可能的分割方案。

示例 1：

** 输入：**s = "aab" ** 输出： [["a","a","b"],["aa","b"]]

示例 2：

** 输入：**s = "a" ** 输出： [["a"]]

回溯 枚举字符串结束位置

var isPalindrome = function(s, left, right) {
    while (left < right) {
        if (s.charAt(left++) !== s.charAt(right--)) {
            return false;
        }
    }
    return true;
}

var partition = function(s) {
    const n = s.length;
    const ans = [];
    const path = [];

    function dfs(i) {
        if (i === n) {
            ans.push(path.slice()); // 复制 path
            return;
        }
        for (let j = i; j < n; j++) { // 枚举子串的结束位置
            if (isPalindrome(s, i, j)) {
                path.push(s.substring(i, j + 1));
                dfs(j + 1);
                path.pop(); // 恢复现场
            }
        }
    }

    dfs(0);
    return ans;
};